GermanWikipedia - /page/entry.mu

<!DOCTYPE html>

<title>Lineare Optimierung</title>

</head>

<h1 id="firstHeading" class="firstHeading mw-first-heading"><span class="mw-page-title-main">Lineare Optimierung</span></h1>

</header>

</div>

<p>Die <b>lineare Optimierung</b> oder <b>lineare Programmierung</b> ist eines der Hauptverfahren des <a href="Operations_Research" title="Operations Research">Operations Research</a> und beschäftigt sich mit der <a href="Optimierung_(Mathematik)" class="mw-redirect" title="Optimierung (Mathematik)">Optimierung</a> <a href="Lineare_Abbildung" title="Lineare Abbildung">linearer Zielfunktionen</a> über einer Menge, die durch lineare <a href="Gleichung" title="Gleichung">Gleichungen</a> und <a href="Ungleichung" title="Ungleichung">Ungleichungen</a> eingeschränkt ist. Häufig lassen sich <i>lineare Programme (LPs)</i> zur Lösung von Problemen einsetzen, für die keine speziell entwickelten Lösungsverfahren bekannt sind, beispielsweise bei der Planung von Verkehrs- oder Telekommunikationsnetzen oder in der Produktionsplanung. Die lineare Optimierung ist ein Spezialfall der <a href="Konvexe_Optimierung" title="Konvexe Optimierung">konvexen Optimierung</a> und Grundlage mehrerer Lösungsverfahren in der <a href="Ganzzahlige_lineare_Optimierung" title="Ganzzahlige lineare Optimierung">ganzzahligen linearen</a> und der <a href="Nichtlineare_Optimierung" title="Nichtlineare Optimierung">nichtlinearen Optimierung</a>. Viele Eigenschaften linearer Programme lassen sich als Eigenschaften von <a href="Polyeder" title="Polyeder">Polyedern</a> interpretieren und auf diese Art geometrisch modellieren und beweisen.

</p><p>Der Begriff „Programmierung“ ist eher im Sinne von „Planung“ zu verstehen als im Sinne der Erstellung eines Computerprogramms. Er wurde schon Mitte der 1940er-Jahre von <a href="George_Dantzig" title="George Dantzig">George Dantzig</a>, einem der Begründer der linearen Optimierung, geprägt, bevor Computer zur Lösung linearer <a href="Optimierungsproblem" title="Optimierungsproblem">Optimierungsprobleme</a> eingesetzt wurden.

</p><p>Aus <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">komplexitätstheoretischer</a> Sicht ist die lineare Optimierung ein einfaches Problem, da es sich beispielsweise mit einigen <a href="Innere-Punkte-Verfahren" title="Innere-Punkte-Verfahren">Innere-Punkte-Verfahren</a> in <a href="Polynomialzeit" title="Polynomialzeit">polynomialer Zeit</a> lösen lässt. In der Praxis hat sich allerdings das <a href="Simplex-Verfahren" title="Simplex-Verfahren">Simplex-Verfahren</a> als einer der schnellsten Algorithmen herausgestellt, obwohl es im schlechtesten Fall exponentielle Laufzeit besitzt. Neben dem eigentlichen Problem löst es immer auch das sogenannte <a href="#Dualität">duale Problem</a> mit, was unter anderem in mehreren Verfahren zur Lösung ganzzahliger linearer Programme ausgenutzt wird.

</p>

<div class="mw-heading mw-heading2"><h2 id="Geschichte">Geschichte</h2></div>

<p>Die Methode der linearen Optimierung wurde 1939 von dem sowjetischen Mathematiker <a href="Leonid_Witaljewitsch_Kantorowitsch" title="Leonid Witaljewitsch Kantorowitsch">Leonid Witaljewitsch Kantorowitsch</a> in seinem Aufsatz „<i>Mathematische Methoden für die Organisation und Planung der Produktion</i>“ eingeführt.<sup id="cite_ref-1" class="reference"><a href="#cite_note-1"><span class="cite-bracket">[</span>1<span class="cite-bracket">]</span></a></sup> Kurz danach veröffentlichte der Amerikaner Frank L. Hitchcock eine Arbeit zu einem <a href="Transportproblem" title="Transportproblem">Transportproblem</a>. Damals erkannte man noch nicht die Bedeutung dieser Arbeiten. Unter anderem für seinen Beitrag zur linearen Optimierung bekam Kantorowitsch aber 1975 den <a href="Nobelpreis" title="Nobelpreis">Nobelpreis</a> für <a href="Wirtschaftswissenschaften" class="mw-redirect" title="Wirtschaftswissenschaften">Wirtschaftswissenschaften</a>.

</p><p>Mitte der 1940er-Jahre erkannte <a href="George_Dantzig" title="George Dantzig">George Dantzig</a>, dass sich viele praktische Beschränkungen durch lineare Ungleichungen beschreiben ließen, und ersetzte erstmals die bis dahin vorherrschenden Faustregeln zur Lösung von Planungsproblemen durch eine (lineare) Zielfunktion. Insbesondere etablierte er damit eine klare Trennung zwischen dem <i>Ziel</i> der Optimierung und den <i>Mitteln</i> zur Lösung des Planungsproblems.

</p><p>Den Durchbruch für die lineare Optimierung schaffte Dantzig 1947, als er eine Arbeit über das <a href="Simplex-Verfahren" title="Simplex-Verfahren">Simplex-Verfahren</a> veröffentlichte, das heute eines der meistgenutzten Verfahren zur Lösung linearer Programme ist.<sup id="cite_ref-2" class="reference"><a href="#cite_note-2"><span class="cite-bracket">[</span>2<span class="cite-bracket">]</span></a></sup> Interesse an dieser Arbeit zeigten zunächst die amerikanischen Militärs, speziell die <a href="United_States_Air_Force" title="United States Air Force">US Air Force</a>, die militärische Einsätze optimieren wollten. In den Folgejahren entwickelten Dantzig, <a href="John_von_Neumann" title="John von Neumann">John von Neumann</a>, <a href="Oskar_Morgenstern" title="Oskar Morgenstern">Oskar Morgenstern</a>, <a href="Tjalling_Koopmans" class="mw-redirect" title="Tjalling Koopmans">Tjalling Koopmans</a> und andere das Verfahren und die zugehörige Theorie weiter und stellten Zusammenhänge zur <a href="Spieltheorie" title="Spieltheorie">Spieltheorie</a> her. Mit dem Aufkommen von <a href="Computer" title="Computer">Computern</a> Mitte der 1950er-Jahre konnte man auch größere Probleme lösen. Etwa ab 1950 entdeckte die Wirtschaft, insbesondere Ölraffinerien, die Anwendungsmöglichkeiten der linearen Optimierung. Ab den 1970er-Jahren profitierte der Simplex-Algorithmus von algorithmischen Fortschritten der <a href="Numerische_lineare_Algebra" title="Numerische lineare Algebra">numerischen linearen Algebra</a>. Insbesondere die Entwicklung numerisch stabiler <a href="Gau%C3%9Fsches_Eliminationsverfahren#LR-Zerlegung" title="Gaußsches Eliminationsverfahren">LR-Zerlegungen</a> zur Lösung großer <a href="Lineares_Gleichungssystem" title="Lineares Gleichungssystem">linearer Gleichungssysteme</a> trugen maßgeblich zum Erfolg und der Verbreitung des Simplex-Verfahrens bei.<sup id="cite_ref-3" class="reference"><a href="#cite_note-3"><span class="cite-bracket">[</span>3<span class="cite-bracket">]</span></a></sup>

</p><p>Im Jahre 1979 veröffentlichte <a href="Leonid_Khachiyan" class="mw-redirect" title="Leonid Khachiyan">Leonid Khachiyan</a> die <a href="Ellipsoidmethode" title="Ellipsoidmethode">Ellipsoidmethode</a>, mit der lineare Programme erstmals – zumindest theoretisch – in <a href="Polynomialzeit" title="Polynomialzeit">Polynomialzeit</a> gelöst werden konnten. 1984 begannen <a href="Narendra_Karmarkar" title="Narendra Karmarkar">Narendra Karmarkar</a> und andere mit der Entwicklung von <a href="Innere-Punkte-Verfahren" title="Innere-Punkte-Verfahren">Innere-Punkte-Verfahren</a> zur Lösung linearer Programme.<sup id="cite_ref-4" class="reference"><a href="#cite_note-4"><span class="cite-bracket">[</span>4<span class="cite-bracket">]</span></a></sup> Diese Algorithmen, die als erste polynomiale Lösungsmethoden auch das Potential zum praktischen Einsatz hatten, wurden innerhalb des nachfolgenden Jahrzehnts noch wesentlich verbessert. Parallel dazu wuchs die Bedeutung des Simplex-Verfahrens zur Lösung von Unterproblemen in der ganzzahligen linearen Optimierung. Anfang der 1990er-Jahre wurden hier noch einmal große Fortschritte durch die Entwicklung neuer <a href="Pivotverfahren" title="Pivotverfahren">Pivotstrategien</a> für den dualen Simplex-Algorithmus erzielt, insbesondere durch das <i>dual steepest edge pricing</i> von John Forrest und Donald Goldfarb.

</p><p>Sowohl das Simplex-Verfahren als auch verschiedene Innere-Punkte-Verfahren sind nach wie vor Gegenstand aktueller Forschung. Die lineare Optimierung wird heute in sehr vielen Bereichen zur Lösung praktischer Probleme eingesetzt. Unter der in praktischen Anwendungen fast immer erfüllten Voraussetzung, dass die auftretenden LP-Matrizen <a href="D%C3%BCnnbesetzte_Matrix" title="Dünnbesetzte Matrix">dünnbesetzt</a> sind (also nur wenige Nicht-Null-Einträge besitzen), können heute lineare Programme mit mehreren hunderttausend Variablen oder Ungleichungen innerhalb weniger Minuten bis Stunden optimal gelöst werden. Die tatsächliche Lösungszeit hängt dabei neben dem verwendeten Lösungsverfahren auch stark von der Anzahl und Anordnung der Nicht-Null-Einträge in der beteiligten Matrix und von der Wahl der Startlösung ab.

</p>

<div class="mw-heading mw-heading2"><h2 id="Problemdefinition">Problemdefinition</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Mathematische_Formulierung">Mathematische Formulierung</h3></div>

<p>Bei einem <i>linearen Programm (LP)</i> sind eine <a href="Matrix_(Mathematik)" title="Matrix (Mathematik)">Matrix</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A\in \mathbb {R} ^{m,n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A\in \mathbb {R} ^{m,n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/328eea35001edb987d3e26c7cd8dceeb7b424007.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:9.38ex; height:2.343ex;" alt="{\displaystyle A\in \mathbb {R} ^{m,n}}" loading="lazy"></span> und zwei <a href="Vektor" title="Vektor">Vektoren</a> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle b\in \mathbb {R} ^{m,1}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle b\in \mathbb {R} ^{m,1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/882c2683ea335f5ac4496303e1c9db2003bb6443.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.471ex; height:2.676ex;" alt="{\displaystyle b\in \mathbb {R} ^{m,1}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\in \mathbb {R} ^{1,n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\in \mathbb {R} ^{1,n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3fcb68d3679857d741d17369f99affb90636929d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:8.023ex; height:2.676ex;" alt="{\displaystyle c\in \mathbb {R} ^{1,n}}" loading="lazy"></span> gegeben. Eine <i>zulässige Lösung</i> ist ein Vektor <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\in \mathbb {R} ^{n}}">

<msup>

</mrow>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\in \mathbb {R} ^{n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/c520ee2cb6ccf8a93c89a8c58a8378796bd52e53.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:7.067ex; height:2.343ex;" alt="{\displaystyle x\in \mathbb {R} ^{n}}" loading="lazy"></span> mit nichtnegativen Einträgen, der die linearen Bedingungen

</p>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{matrix}a_{11}x_{1}&+\ldots &+a_{1n}x_{n}&\leq b_{1}\\a_{21}x_{1}&+\ldots &+a_{2n}x_{n}&\leq b_{2}\\\vdots &\vdots &\vdots &\vdots \\a_{m1}x_{1}&+\ldots &+a_{mn}x_{n}&\leq b_{m}\end{matrix}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7e7d93d8181a261350f40ba622ee72eeb73ad7fe.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -6.338ex; width:32.122ex; height:13.843ex;" alt="{\displaystyle {\begin{matrix}a_{11}x_{1}&+\ldots &+a_{1n}x_{n}&\leq b_{1}\\a_{21}x_{1}&+\ldots &+a_{2n}x_{n}&\leq b_{2}\\\vdots &\vdots &\vdots &\vdots \\a_{m1}x_{1}&+\ldots &+a_{mn}x_{n}&\leq b_{m}\end{matrix}}}" loading="lazy"></span></dd></dl>

<p>erfüllt. Ziel ist es, unter allen zulässigen Vektoren <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> einen zu finden, der das <a href="Standardskalarprodukt" title="Standardskalarprodukt">Standardskalarprodukt</a>

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle cx=c_{1}x_{1}+\ldots +c_{n}x_{n}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7fc5c66e6374b1913240b2aa71e676acc06ec333.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:23.057ex; height:2.343ex;" alt="{\displaystyle cx=c_{1}x_{1}+\ldots +c_{n}x_{n}}" loading="lazy"></span></dd></dl>

<p>maximiert. Dieses Optimierungsproblem in der sogenannten <i>Standardform</i> (auch als <i>Ungleichungsform</i> bezeichnet) wird oft abkürzend als

</p>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max\{cx\;|\;Ax\leq b,x\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/371f96ca1bd9dfb80238d03d50d6cd3262ecb12a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:24.718ex; height:2.843ex;" alt="{\displaystyle \max\{cx\;|\;Ax\leq b,x\geq 0\}}" loading="lazy"></span></dd></dl>

<p>geschrieben, wobei die Bedingungen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Ax\leq b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Ax\leq b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/08249140bbb640be6c1242b705a896fb8951886f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.169ex; height:2.343ex;" alt="{\displaystyle Ax\leq b}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a2608e2b392b079f5b763f27bf52883dbee3b64a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.591ex; height:2.343ex;" alt="{\displaystyle x\geq 0}" loading="lazy"></span> komponentenweise zu verstehen sind.

</p><p>Darüber hinaus gibt es noch weitere äquivalente Formulierungen, die sich durch einfache Operationen in diese Standardform bringen lassen:

</p>

<ul><li>Minimierungsproblem statt Maximierungsproblem: Multiplikation des Zielfunktionsvektors <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span> mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/704fb0427140d054dd267925495e78164fee9aac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.971ex; height:2.343ex;" alt="{\displaystyle -1}" loading="lazy"></span></li>

<li>Größer-gleich- statt Kleiner-gleich-Bedingungen: Multiplikation der entsprechenden Ungleichungen mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/704fb0427140d054dd267925495e78164fee9aac.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:2.971ex; height:2.343ex;" alt="{\displaystyle -1}" loading="lazy"></span></li>

<li>Gleichheitsbedingungen statt Ungleichheitsbedingungen: Ersetzung von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}x=b_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}x=b_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6909b4e800e82002bade68281faadd5b3d5355ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.255ex; height:2.509ex;" alt="{\displaystyle a_{i}x=b_{i}}" loading="lazy"></span> durch <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}x\leq b_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}x\leq b_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7a1bf1f297cda4192968832603e62d5e11610d21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.255ex; height:2.509ex;" alt="{\displaystyle a_{i}x\leq b_{i}}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle -a_{i}x\leq -b_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle -a_{i}x\leq -b_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/53be286f59670c729aeb6bb33d6634e1649d2e24.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:11.871ex; height:2.509ex;" alt="{\displaystyle -a_{i}x\leq -b_{i}}" loading="lazy"></span></li>

<li>Variablen ohne Nichtnegativitätsbedingung: Ersetzung von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> durch <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x'-x''}">

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x'-x''}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/36f9ec3cbb2d15c4eabc41aae8728c460c7b4946.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.322ex; height:2.676ex;" alt="{\displaystyle x'-x''}" loading="lazy"></span> mit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x',x''\geq 0}">

<msup>

</msup>

<msup>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x',x''\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2cc9bba46db5407966a3717bf8e4a1fe9ac6b4a0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.776ex; height:2.843ex;" alt="{\displaystyle x',x''\geq 0}" loading="lazy"></span></li></ul>

<p>Die lineare Optimierung behandelt nur Probleme, bei denen die Variablen beliebige reelle Zahlen annehmen dürfen. Ein <i>(gemischt-)ganzzahliges lineares Programm</i>, bei dem einige Variablen nur ganzzahlige Werte annehmen dürfen, ist <i>kein Spezialfall</i>, sondern – im Gegenteil – eine Verallgemeinerung. Solche Optimierungsprobleme sind im Allgemeinen <a href="NP-%C3%84quivalenz" title="NP-Äquivalenz">NP-äquivalent</a>, d. h. <a href="P-NP-Problem" title="P-NP-Problem">vermutlich</a> nicht effizient lösbar. Dieser Fall wird von der <a href="Ganzzahlige_lineare_Optimierung" title="Ganzzahlige lineare Optimierung">ganzzahligen linearen Optimierung</a> behandelt.

</p>

<div class="mw-heading mw-heading3"><h3 id="Geometrische_Interpretation">Geometrische Interpretation</h3></div>

<p>Ein lineares Programm lässt sich geometrisch interpretieren. Wenn <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}x\leq b_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}x\leq b_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7a1bf1f297cda4192968832603e62d5e11610d21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.255ex; height:2.509ex;" alt="{\displaystyle a_{i}x\leq b_{i}}" loading="lazy"></span> die i. Zeile eines linearen Programms in Standardform ist, dann beschreibt die Menge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{x\;|\;a_{i}x=b_{i}\}}">

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{x\;|\;a_{i}x=b_{i}\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/73de67bfd3d799166ea4b667bc358ab9cb2358fb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.847ex; height:2.843ex;" alt="{\displaystyle \{x\;|\;a_{i}x=b_{i}\}}" loading="lazy"></span> aller Punkte <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span>, die die zugehörige lineare Gleichung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}x=b_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}x=b_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6909b4e800e82002bade68281faadd5b3d5355ba.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.255ex; height:2.509ex;" alt="{\displaystyle a_{i}x=b_{i}}" loading="lazy"></span> erfüllen, eine <a href="Hyperebene" title="Hyperebene">Hyperebene</a> im <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>-dimensionalen Raum. Die Menge der Punkte, die die lineare Ungleichung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}x\leq b_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}x\leq b_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7a1bf1f297cda4192968832603e62d5e11610d21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.255ex; height:2.509ex;" alt="{\displaystyle a_{i}x\leq b_{i}}" loading="lazy"></span> erfüllen, besteht aus allen Punkten auf der einen Seite der Hyperebene (inklusive der Hyperebene selbst), bildet also einen <a href="Halbraum" title="Halbraum">Halbraum</a>. Jede Zeile <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle a_{i}x\leq b_{i}}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle a_{i}x\leq b_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7a1bf1f297cda4192968832603e62d5e11610d21.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:8.255ex; height:2.509ex;" alt="{\displaystyle a_{i}x\leq b_{i}}" loading="lazy"></span> teilt daher den <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>-dimensionalen Raum in zwei Hälften, wobei die Punkte in der einen Hälfte zulässig sind und in der anderen nicht. Die Menge

</p>

</mrow>

</mrow>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P:=\{x\;|\;Ax\leq b,\;x\geq 0\}=\{x\;|\;a_{i}x\leq b_{i},\;i=1,\ldots ,m,\;x\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/25d92977bbc4fe921ceaeaddde9b96eaa699e62c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:63.697ex; height:2.843ex;" alt="{\displaystyle P:=\{x\;|\;Ax\leq b,\;x\geq 0\}=\{x\;|\;a_{i}x\leq b_{i},\;i=1,\ldots ,m,\;x\geq 0\}}" loading="lazy"></span></dd></dl>

<p>der Punkte, die alle Ungleichungen des LPs erfüllen, ist genau der <a href="Schnittmenge#Schnittmenge" class="mw-redirect" title="Schnittmenge">Schnitt</a> dieser Halbräume, also die Menge aller Punkte, die für jede Ungleichung in der jeweiligen zulässigen Hälfte des Raumes liegen. Diese Lösungsmenge <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"></span> des linearen Programms bildet ein <a href="Konvexe_Menge" title="Konvexe Menge">konvexes</a> <a href="Polyeder" title="Polyeder">Polyeder</a>, also ein <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle n}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle n}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a601995d55609f2d9f5e233e36fbe9ea26011b3b.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.395ex; height:1.676ex;" alt="{\displaystyle n}" loading="lazy"></span>-dimensionales Vieleck, in dem die Verbindungslinie zwischen zwei beliebigen Punkten von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"></span> vollständig in <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle P}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle P}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b4dc73bf40314945ff376bd363916a738548d40a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.745ex; height:2.176ex;" alt="{\displaystyle P}" loading="lazy"></span> enthalten ist. Ziel der Optimierung ist es, unter allen Punkten des Polyeders einen zu finden, der die lineare Funktion <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c\colon \,x\to c^{T}x}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c\colon \,x\to c^{T}x}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/00f5be9529bd5c466dd0d206c55aacc0c4e762fd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:11.097ex; height:2.676ex;" alt="{\displaystyle c\colon \,x\to c^{T}x}" loading="lazy"></span> maximiert. Geometrisch entspricht dies der Verschiebung der Hyperebene <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \{x\;|\;c^{T}x=0\}}">

</mrow>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \{x\;|\;c^{T}x=0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b32bcb4a3816c8c1a24cd0d8042b501dfbf42796.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:13.578ex; height:3.176ex;" alt="{\displaystyle \{x\;|\;c^{T}x=0\}}" loading="lazy"></span> in Richtung des Vektors <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span>, bis die verschobene Hyperebene das Polyeder gerade noch <a href="Ber%C3%BChrung_(Mathematik)" title="Berührung (Mathematik)">berührt</a>. Die Menge aller Berührungspunkte ist genau die Menge der Optimallösungen des linearen Programms.

</p>

<p>Im nebenstehenden Bild ist diese Anordnung für den Fall von nur zwei Variablen dargestellt. Eine Hyperebene im zweidimensionalen Raum ist eine <a href="Gerade" title="Gerade">Gerade</a>, im Bild grün dargestellt. Jede dieser Geraden teilt den Raum in eine zulässige und eine unzulässige Hälfte. Die Menge der Punkte, die auf der zulässigen Seite jeder Geraden liegen, bilden das blau dargestellte Polyeder (Vieleck). Die rote Gerade stellt die Zielfunktion dar. Ziel ist es, sie so weit wie möglich in Richtung des roten Vektors <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/86a67b81c2de995bd608d5b2df50cd8cd7d92455.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.007ex; height:1.676ex;" alt="{\displaystyle c}" loading="lazy"></span> zu verschieben, ohne das Polyeder zu verlassen. Im nebenstehenden Bild ist der rote Berührungspunkt der Zielfunktionsgeraden mit dem Polyeder die einzige Optimallösung.

</p>

<div class="mw-heading mw-heading2"><h2 id="Beispiel_aus_der_Produktionsplanung_(zweidimensional)"><span id="Beispiel_aus_der_Produktionsplanung_.28zweidimensional.29"></span>Beispiel aus der Produktionsplanung (zweidimensional)</h2></div>

<p>Ein Unternehmen stellt zwei verschiedene Produkte her, für deren Fertigung drei Maschinen A, B, C zur Verfügung stehen. Diese Maschinen haben eine maximale monatliche Laufzeit (Kapazität) von 170 Stunden (A), 150 Stunden (B) bzw. 180 Stunden (C). Eine Mengeneinheit (ME) von Produkt 1 liefert einen <a href="Deckungsbeitrag" title="Deckungsbeitrag">Deckungsbeitrag</a> von 300 Euro, eine ME von Produkt 2 dagegen 500 Euro. Fertigt man eine ME von Produkt 1, dann benötigt man dafür eine Stunde die Maschine A und eine Stunde die Maschine B. Eine Einheit von Produkt 2 belegt zwei Stunden lang Maschine A, eine Stunde Maschine B und drei Stunden Maschine C. Ziel ist es, Produktionsmengen zu bestimmen, die den Deckungsbeitrag des Unternehmens maximieren, ohne die Maschinenkapazitäten zu überschreiten. Fixkosten können in dem Optimierungsproblem ignoriert und anschließend addiert werden, da sie per Definition unabhängig von den zu bestimmenden Produktionsmengen sind.

</p>

<div class="mw-heading mw-heading3"><h3 id="Mathematische_Modellierung">Mathematische Modellierung</h3></div>

<p>Angenommen, der Betrieb fertigt pro Monat <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a8788bf85d532fa88d1fb25eff6ae382a601c308.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{1}}" loading="lazy"></span> ME von Produkt 1 und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{2}}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{2}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/d7af1b928f06e4c7e3e8ebfd60704656719bd766.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.384ex; height:2.009ex;" alt="{\displaystyle x_{2}}" loading="lazy"></span> ME von Produkt 2. Dann beträgt der Gesamtdeckungsbeitrag

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(x_{1},x_{2})=300x_{1}+500x_{2}.}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1b37daa3f7c88274903b8fb3664caf8d34e1804f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.766ex; height:2.843ex;" alt="{\displaystyle G(x_{1},x_{2})=300x_{1}+500x_{2}.}" loading="lazy"></span></dd></dl>

<p>Diesen Wert möchte das Unternehmen maximieren. Da die Maschinenkapazitäten eingehalten werden müssen, ergeben sich die Nebenbedingungen:

</p>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<mtext> (Maschine A, rechts in schwarz eingezeichnet)</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<mtext> (Maschine B, rechts in tuerkis eingezeichnet)</mtext>

</mrow>

</mtd>

</mtr>

<mtr>

<mtd>

<msub>

</mrow>

</msub>

</mtd>

<mtd>

</mtd>

<mtd>

<mtext> (Maschine C, rechts in violett eingezeichnet)</mtext>

</mrow>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{alignedat}{3}x_{1}&+&2x_{2}&\leq 170&&{\text{ (Maschine A, rechts in schwarz eingezeichnet)}}\\x_{1}&+&x_{2}&\leq 150&&{\text{ (Maschine B, rechts in tuerkis eingezeichnet)}}\\&&3x_{2}&\leq 180&&{\text{ (Maschine C, rechts in violett eingezeichnet)}}\end{alignedat}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0f79fa9ec9a268b6fb0571c95d950c2fdf49189c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -4.005ex; width:61.753ex; height:9.176ex;" alt="{\displaystyle {\begin{alignedat}{3}x_{1}&+&2x_{2}&\leq 170&&{\text{ (Maschine A, rechts in schwarz eingezeichnet)}}\\x_{1}&+&x_{2}&\leq 150&&{\text{ (Maschine B, rechts in tuerkis eingezeichnet)}}\\&&3x_{2}&\leq 180&&{\text{ (Maschine C, rechts in violett eingezeichnet)}}\end{alignedat}}}" loading="lazy"></span></dd></dl>

<p>Da außerdem keine negativen Produktionsmengen möglich sind, muss <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1},x_{2}\geq 0}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1},x_{2}\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b668e0a1d484fae37d9d1375b63fdb0d4a38bf4f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:10.063ex; height:2.509ex;" alt="{\displaystyle x_{1},x_{2}\geq 0}" loading="lazy"></span> gelten (Nichtnegativitätsbedingung).

</p>

<div class="mw-heading mw-heading3"><h3 id="Geometrische_Interpretation_als_Polyeder">Geometrische Interpretation als Polyeder</h3></div>

<p>Im nebenstehenden Bild sind die Ungleichungen aus dem obigen Beispiel als türkise, schwarze und violette Beschränkungen eingezeichnet. Zusammen definieren sie das (blau umrandete) <a href="Polyeder" title="Polyeder">Polyeder</a> der zulässigen Punkte. Die rotgestrichelten Linien stellen Iso-Gewinnfunktionen dar, d. h., alle Punkte auf einer solchen Linie haben denselben Zielfunktionswert. Da das Unternehmen möglichst viel Gewinn erzielen will, ist das Ziel der Optimierung, solch eine rot gestrichelte Linie so weit nach rechts oben zu schieben, dass sie gerade noch das Polyeder berührt. Alle Berührungspunkte sind dann optimal. In diesem Fall ist der Punkt (130,20) die eindeutige optimale <a href="Ecke" title="Ecke">Ecke</a>, und der optimale Zielfunktionswert beträgt 49.000 Euro.

</p><p>Im Allgemeinen ist die Optimallösung eines linearen Optimierungsproblems allerdings weder eindeutig noch ganzzahlig. Wenn beispielsweise beide Produkte den gleichen Deckungsbeitrag hätten, wären die roten Iso-Gewinnfunktionen parallel zur Ungleichung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{1}+x_{2}\leq 150}">

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}+x_{2}\leq 150}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1d15724af229424eb4441a430990759ee8a2a16c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:14.194ex; height:2.509ex;" alt="{\displaystyle x_{1}+x_{2}\leq 150}" loading="lazy"></span>. In diesem Fall wäre jeder Punkt auf der Strecke zwischen (130,20) und (150,0) optimal, es gäbe also unendlich viele Optimallösungen.

</p>

<div class="mw-heading mw-heading2"><h2 id="Anwendungen">Anwendungen</h2></div>

<p>Die lineare Optimierung hat viele Anwendungen in der Praxis, von denen hier einige beispielhaft vorgestellt werden sollen.

</p>

<div class="mw-heading mw-heading3"><h3 id="Produktionsplanung">Produktionsplanung</h3></div>

<p>Wie in dem obigen Beispiel kann ein Unternehmen eine Reihe von Produkten mit bekanntem <a href="Deckungsbeitrag" title="Deckungsbeitrag">Deckungsbeitrag</a> herstellen. Die Herstellung einer Einheit jedes dieser Produkte benötigt eine bekannte Menge an beschränkten Ressourcen (Produktionskapazität, Rohmaterialien, Arbeitszeit etc.). Die Aufgabe ist die Erstellung eines <a href="Produktionsprogramm" title="Produktionsprogramm">Produktionsprogramms</a>, d. h. die Festlegung, wie viel von jedem Produkt produziert werden soll, so dass der Gewinn des Unternehmens maximiert wird, ohne die Ressourcenbeschränkungen zu verletzen. Ein weiteres Beispiel sind <a href="Zuschnittsproblem" class="mw-redirect" title="Zuschnittsproblem">Zuschnittsprobleme</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Mischungsprobleme">Mischungsprobleme</h3></div>

<p>Eine ähnliche Anwendung sind Mischungsprobleme, bei denen es darum geht, Zutaten zu einem Endprodukt zusammenzustellen, wobei die Menge der jeweiligen Zutaten innerhalb eines bestimmten Bereichs variiert werden kann. Ein Beispiel hierfür ist das 1947 von George Dantzig untersuchte <i>Diät-Problem:</i> Gegeben sind eine Reihe von Rohmaterialien (z. B. Hafer, Schweinefleisch, Sonnenblumenöl etc.) zusammen mit ihrem Gehalt an bestimmten Nährwerten (z. B. Eiweiß, Fett, Vitamin A etc.) und ihrem Preis pro Kilogramm. Die Aufgabe besteht darin, eines oder mehrere Endprodukte mit minimalen Kosten aus den Rohmaterialien zu mischen, unter der <a href="Nebenbedingung" title="Nebenbedingung">Nebenbedingung</a>, dass bestimmte Mindest- und Höchstgrenzen für die einzelnen Nährwerte eingehalten werden. Auch bei Schmelzvorgängen treten solche Mischungsprobleme auf, wie z. B. in der Stahlherstellung.

</p>

<div class="mw-heading mw-heading3"><h3 id="Routing_in_Telekommunikations-_oder_Verkehrsnetzen">Routing in Telekommunikations- oder Verkehrsnetzen</h3></div>

<p>Ein klassisches Anwendungsgebiet der linearen Optimierung ist die Bestimmung eines <a href="Routing" title="Routing">Routings</a> für Verkehrsanforderungen in <a href="Telekommunikationsnetz" class="mw-redirect" title="Telekommunikationsnetz">Telekommunikations-</a> oder Verkehrsnetzen, oft in Verbindung mit Kapazitätsplanung. Dabei müssen Verkehrsflüsse so durch ein Netz geroutet werden, dass alle Verkehrsanforderungen erfüllt werden, ohne die Kapazitätsbedingungen zu verletzen. Diese sogenannten <i>Mehrgüterflüsse</i> (englisch <i>multicommodity flow</i>) sind ein Beispiel für ein Problem, das mit linearer Optimierung gut lösbar ist, für das aber im allgemeinen Fall kein exakter Algorithmus bekannt ist, der nicht auf LP-Theorie basiert.

</p>

<div class="mw-heading mw-heading3"><h3 id="Spieltheorie">Spieltheorie</h3></div>

<div class="hauptartikel" role="navigation"><span class="hauptartikel-pfeil" title="siehe" aria-hidden="true" role="presentation">→ </span><i><span class="hauptartikel-text">Hauptartikel</span>: <a href="Lineare_Optimierung_(Spieltheorie)" title="Lineare Optimierung (Spieltheorie)">Lineare Optimierung (Spieltheorie)</a></i></div>

<p>Innerhalb der mathematischen <a href="Spieltheorie" title="Spieltheorie">Spieltheorie</a> kann die lineare Optimierung dazu verwendet werden, optimale Strategien in Zwei-Personen-<a href="Nullsummenspiel" title="Nullsummenspiel">Nullsummenspielen</a> zu berechnen. Dabei wird für jeden Spieler eine <a href="Wahrscheinlichkeitsverteilung" class="mw-redirect" title="Wahrscheinlichkeitsverteilung">Wahrscheinlichkeitsverteilung</a> berechnet, bei der es sich um ein zufälliges Mischungsverhältnis seiner Strategien handelt. „Würfelt“ ein Spieler seine Strategie gemäß dieser Wahrscheinlichkeitsverteilung zufällig aus, ist ihm die bestmögliche Gewinnerwartung sicher, die er haben kann, wenn er seine Strategie unabhängig von der seines Gegners wählt.

</p>

<div class="mw-heading mw-heading3"><h3 id="Nichtlineare_und_gemischt-ganzzahlige_Optimierung">Nichtlineare und gemischt-ganzzahlige Optimierung</h3></div>

<p>Viele Anwendungsprobleme lassen sich mit kontinuierlichen Variablen nicht sinnvoll modellieren, sondern erfordern die Ganzzahligkeit einiger Variablen. Beispielsweise können keine 3,7 Flugzeuge gekauft werden, sondern nur eine ganze Anzahl, und ein Bus kann nur ganz oder gar nicht fahren, aber nicht zu zwei Dritteln. Bei der Verwendung von <a href="Branch-and-Cut" title="Branch-and-Cut">Branch-and-Cut</a> zur Lösung solcher <a href="Ganzzahlige_lineare_Optimierung" title="Ganzzahlige lineare Optimierung">ganzzahliger</a> bzw. <a href="Gemischt-ganzzahlige_Optimierung#Gemischt-ganzzahlige_lineare_Optimierungsprobleme" title="Gemischt-ganzzahlige Optimierung">gemischt-ganzzahliger linearer Optimierungsprobleme</a> müssen sehr viele ähnliche lineare Programme hintereinander als Unterproblem gelöst werden. Eine optimale ganzzahlige Lösung eines linearen Programms zu finden ist <a href="NP-Vollst%C3%A4ndigkeit" title="NP-Vollständigkeit">NP-vollständig</a>, aber <a href="Parametrisierter_Algorithmus" title="Parametrisierter Algorithmus">parametrisierbar</a> in der Anzahl der Variablen. Es ist sogar NP-vollständig, irgendeine ganzzahlige Lösung eines linearen Programms zu finden. Eine Ausnahme ist hier, wenn die Restriktionsmenge durch eine <a href="Total_unimodulare_Matrix" title="Total unimodulare Matrix">total unimodulare Matrix</a> gegeben ist, dann sind alle Ecken des Polyeders ganzzahlig.

Auch zur Lösung <a href="Nichtlineare_Optimierung" title="Nichtlineare Optimierung">nichtlinearer Optimierungsprobleme</a> gibt es Algorithmen, in denen lineare Programme als Unterproblem gelöst werden müssen (z. B. <i>Sequential Linear Programming</i>).

</p>

<div class="sieheauch" role="navigation" style="font-style:italic;"><span class="sieheauch-text">Siehe auch</span>: <a href="Gemischt-ganzzahlige_Optimierung" title="Gemischt-ganzzahlige Optimierung">Gemischt-ganzzahlige Optimierung</a>, <a href="Ganzzahlige_lineare_Optimierung" title="Ganzzahlige lineare Optimierung">Ganzzahlige lineare Optimierung</a> und <a href="Nichtlineare_Optimierung" title="Nichtlineare Optimierung">Nichtlineare Optimierung</a></div>

<div class="mw-heading mw-heading2"><h2 id="Lösbarkeit_aus_theoretischer_Sicht"><span id="L.C3.B6sbarkeit_aus_theoretischer_Sicht"></span>Lösbarkeit aus theoretischer Sicht</h2></div>

<p>Ein lineares Programm hat nicht immer eine Optimallösung. Drei Fälle sind zu unterscheiden:

</p>

<ol><li>Das LP ist <i>unzulässig</i>, weil sich Ungleichungen widersprechen (z. B. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\leq 1}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\leq 1}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/97bc1f8c61d5129d13278e6ee53069a1736ce3c0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.591ex; height:2.343ex;" alt="{\displaystyle x\leq 1}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\geq 2}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\geq 2}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6e5e4cf59b5136062d043f79c2bf0c6af0443c1a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.591ex; height:2.343ex;" alt="{\displaystyle x\geq 2}" loading="lazy"></span>). In diesem Fall gibt es keine Lösung, die alle Ungleichungen erfüllt, d. h., das zugehörige Polyeder ist die <a href="Leere_Menge" title="Leere Menge">leere Menge</a>.</li>

<li>Das LP ist unbeschränkt, d. h., es gibt unendlich viele zulässige Lösungen mit beliebig hohen Zielfunktionswerten (z. B. <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max\{x\;|\;x\geq 0\}}">

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max\{x\;|\;x\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/bb6e1b070c445e3d7ea79c775222de4e3b3bfb43.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:15.508ex; height:2.843ex;" alt="{\displaystyle \max\{x\;|\;x\geq 0\}}" loading="lazy"></span>).</li>

<li>Das LP besitzt mindestens eine Optimallösung. Dies ist beispielsweise gegeben, falls das zugehörige Polyeder beschränkt, also ein <a href="Polytop_(Geometrie)" title="Polytop (Geometrie)">Polytop</a>, und nichtleer ist.</li></ol>

<p>Die Menge der Optimallösungen bildet eine Seitenfläche (<a href="Ecke" title="Ecke">Ecke</a>, Kante,…) des Polyeders, so dass es entweder keine, genau eine oder unendlich viele Optimallösungen gibt. Wenn das LP lösbar und beschränkt ist, gibt es immer eine optimale Ecke, also einen optimalen Punkt, der nicht aus anderen Punkten des Polyeders <a href="Linearkombination" title="Linearkombination">konvex kombiniert</a> werden kann. Diese Eigenschaft macht sich unter anderem das <a href="Simplex-Verfahren" title="Simplex-Verfahren">primale Simplex-Verfahren</a> zunutze.

</p>

<div class="mw-heading mw-heading2"><h2 id="Komplexität_und_Lösungsverfahren"><span id="Komplexit.C3.A4t_und_L.C3.B6sungsverfahren"></span>Komplexität und Lösungsverfahren</h2></div>

<p>Das Finden einer Optimallösung bzw. die Feststellung, dass ein LP keine Lösung besitzt, ist mit Hilfe von <a href="#Innere-Punkte-Verfahren">Innere-Punkte-Verfahren</a> oder der <a href="#Ellipsoidmethode">Ellipsoidmethode</a> in <a href="Polynomialzeit" title="Polynomialzeit">Polynomialzeit</a> möglich, so dass die Lineare Optimierung aus Sicht der <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">Komplexitätstheorie</a> ein leicht lösbares Problem ist. Aus praktischer Sicht ist jedoch oft das Simplex-Verfahren schneller, obwohl es theoretisch exponentielle Laufzeit besitzt. Es ist bis heute unbekannt, ob es einen <i>streng polynomialen</i> Algorithmus zur Lösung allgemeiner linearer Programme gibt, also einen Algorithmus, dessen Laufzeit nicht von der Größe der auftretenden Zahlen abhängt.

</p>

<div class="mw-heading mw-heading3"><h3 id="Simplex-Verfahren">Simplex-Verfahren</h3></div>

<div class="hauptartikel" role="navigation"><span class="hauptartikel-pfeil" title="siehe" aria-hidden="true" role="presentation">→ </span><i><span class="hauptartikel-text">Hauptartikel</span>: <a href="Simplex-Verfahren" title="Simplex-Verfahren">Simplex-Verfahren</a></i></div>

<p>Das <i>Simplex-Verfahren</i> ist ein <a href="Pivotverfahren" title="Pivotverfahren">Basisaustauschverfahren</a>, das im Jahre 1947 von <a href="George_Dantzig" title="George Dantzig">George Dantzig</a> entwickelt und seitdem wesentlich verbessert wurde; es ist der wichtigste Algorithmus zur Lösung linearer Programme in der Praxis. Die Grundidee besteht darin, von einer Ecke des <a href="Polyeder" title="Polyeder">Polyeders</a> zu einer benachbarten Ecke mit besserem Zielfunktionswert zu laufen, bis dies nicht mehr möglich ist. Da es sich bei der linearen Optimierung um ein <a href="Konvexe_Optimierung" title="Konvexe Optimierung">konvexes Optimierungsproblem</a> handelt, ist die damit erreichte lokal optimale Ecke auch global optimal. Das Verfahren ist im nebenstehenden Bild illustriert: Ziel ist es, einen möglichst weit oben liegenden Punkt des Polyeders zu finden. In roter Farbe ist ein möglicher Pfad des Simplex-Verfahrens entlang der Ecken des Polyeders dargestellt, wobei sich der Zielfunktionswert mit jedem Schritt verbessert.

</p><p>Aus komplexitätstheoretischer Sicht benötigt der Simplex-Algorithmus im schlechtesten Fall exponentielle Laufzeit. Für jede Variante des Algorithmus konnte bisher ein Beispiel konstruiert werden, bei dem der Algorithmus alle Ecken des Polyeders abläuft, meist basierend auf dem <i>Klee-Minty-Würfel</i>.<sup id="cite_ref-5" class="reference"><a href="#cite_note-5"><span class="cite-bracket">[</span>5<span class="cite-bracket">]</span></a></sup> Aus praktischer Sicht sind solche Fälle allerdings sehr selten. Bei sogenannten <i>entarteten</i> linearen Programmen, bei denen eine Ecke durch mehr Ungleichungen definiert wird als unbedingt nötig (beispielsweise durch drei Ungleichungen im zweidimensionalen Raum), kann es allerdings passieren, dass der Algorithmus, wie in <a href="Pivotverfahren#Kreislaufanfällige_Pivotauswahlregel" title="Pivotverfahren">diesem Beispiel</a>, immer wieder dieselbe Ecke betrachtet, anstatt zur nächsten Ecke zu wechseln. Dieses Problem tritt bei praktischen Planungsproblemen häufig auf und kann dazu führen, dass der Algorithmus nicht terminiert oder der Zielfunktionswert sich über viele Iterationen hinweg nicht verbessert. Gute Simplex-Implementierungen entdecken solche Fälle und behandeln sie beispielsweise durch eine leichte Perturbation (absichtliche numerische Störung) des Problems, die später wieder rückgängig gemacht wird.

</p><p>Unter der Voraussetzung, dass die Matrix <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span> <a href="D%C3%BCnnbesetzte_Matrix" title="Dünnbesetzte Matrix">dünnbesetzt</a> ist (d. h. nur wenige Koeffizienten ungleich Null enthält), was in der Praxis fast immer der Fall ist, können mit dem Simplex-Verfahren heute sehr große LPs in annehmbarer Zeit optimal gelöst werden. Ein großer Vorteil des Simplex-Verfahrens besteht darin, dass es nach dem Hinzufügen einer Ungleichung oder Variable im LP oder nach einer leichten Änderung der Koeffizienten einen „Warmstart“ von einer vorher bereits erreichten Ecke aus durchführen kann, so dass nur wenige Iterationen zum erneuten Finden einer Optimallösung notwendig sind. Dies ist insbesondere im Zusammenhang mit <a href="Schnittebenenverfahren" title="Schnittebenenverfahren">Schnittebenenverfahren</a> oder <a href="Branch-and-Cut" title="Branch-and-Cut">Branch-and-Cut</a> zur Lösung ganzzahliger linearer Programme von großer Bedeutung, wo sehr viele ähnliche LPs in Serie gelöst werden müssen.

</p>

<div class="mw-heading mw-heading3"><h3 id="Innere-Punkte-Verfahren">Innere-Punkte-Verfahren</h3></div>

<div class="hauptartikel" role="navigation"><span class="hauptartikel-pfeil" title="siehe" aria-hidden="true" role="presentation">→ </span><i><span class="hauptartikel-text">Hauptartikel</span>: <a href="Innere-Punkte-Verfahren" title="Innere-Punkte-Verfahren">Innere-Punkte-Verfahren</a></i></div>

<p><i>Innere-Punkte-Verfahren</i>, auch <i>Barrier-Verfahren</i> genannt, nähern sich einer optimalen Ecke durch das Innere des Polyeders (siehe Bild). Der erste solche Algorithmus wurde 1984 von <a href="Narendra_Karmarkar" title="Narendra Karmarkar">Narendra Karmarkar</a> beschrieben. Seine Bedeutung lag vor allem darin, dass er der erste polynomiale Algorithmus zum Lösen linearer Programme war, der das Potential hatte, auch praktisch einsetzbar zu sein. Die entscheidenden Durchbrüche, die Innere-Punkte-Verfahren konkurrenzfähig zum Simplex-Algorithmus machten, wurden aber erst in den 1990er-Jahren erzielt. Ein Vorteil dieser Verfahren ist, dass sie, im Gegensatz zum Simplex-Verfahren, in leichter Abwandlung auch zum Lösen <a href="Quadratische_Programmierung" class="mw-redirect" title="Quadratische Programmierung">quadratischer</a> oder bestimmter <a href="Nichtlineare_Optimierung" title="Nichtlineare Optimierung">nichtlinearer Programme</a> eingesetzt werden können. Des Weiteren sind sie für große, dünnbesetzte Probleme häufig dem Simplex-Verfahren überlegen. Ein Nachteil ist, dass sie sich nach dem Hinzufügen einer Nebenbedingung oder Variablen im LP bei weitem nicht so effizient „warmstarten“ lassen wie das Simplex-Verfahren.

</p>

<div class="mw-heading mw-heading3"><h3 id="Ellipsoidmethode">Ellipsoidmethode</h3></div>

<div class="hauptartikel" role="navigation"><span class="hauptartikel-pfeil" title="siehe" aria-hidden="true" role="presentation">→ </span><i><span class="hauptartikel-text">Hauptartikel</span>: <a href="Ellipsoidmethode" title="Ellipsoidmethode">Ellipsoidmethode</a></i></div>

<p>Die <i>Ellipsoidmethode</i> wurde ursprünglich in den Jahren 1976 und 1977 von <a href="David_Yudin" class="mw-redirect" title="David Yudin">David Yudin</a> und <a href="Arkadi_Nemirovski" title="Arkadi Nemirovski">Arkadi Nemirovski</a> und unabhängig davon von <a href="Naum_Schor" title="Naum Schor">Naum Schor</a> zur Lösung <a href="Konvexe_Optimierung" title="Konvexe Optimierung">konvexer Optimierungsprobleme</a> entwickelt. Im Jahre 1979 modifizierte der sowjetische Mathematiker <a href="Leonid_Khachiyan" class="mw-redirect" title="Leonid Khachiyan">Leonid Khachiyan</a> das Verfahren und entwickelte damit den ersten <a href="Polynomialzeit" title="Polynomialzeit">polynomialen</a> Algorithmus zur Lösung linearer Programme. Für praktische Zwecke ist er allerdings nicht geeignet. Die Ellipsoidmethode dient dazu, einen beliebigen Punkt in einem volldimensionalen Polyeder zu finden oder festzustellen, dass das Polyeder leer ist. Da man zeigen kann, dass die Lösung eines LPs äquivalent ist zum Finden eines zulässigen Punktes in einem geeignet definierten Hilfspolyeder, lässt sich mit Hilfe der Ellipsoidmethode (theoretisch) auch ein LP lösen.

</p><p>Die Grundidee des Verfahrens besteht darin, ein <a href="Ellipsoid" title="Ellipsoid">Ellipsoid</a> (im Bild rot) zu definieren, das alle Ecken des Polyeders (blau) enthält. Anschließend wird festgestellt, ob der Mittelpunkt dieses Ellipsoids im Polyeder enthalten ist. Falls ja, hat man einen Punkt im Polyeder gefunden und kann aufhören. Andernfalls kann man das Halbellipsoid bestimmen, in dem das Polyeder enthalten sein muss, und ein neues, kleineres Ellipsoid um das Polyeder legen (im Bild grün). Nach einer Anzahl von Schritten, die polynomial von der Kodierungslänge des LPs abhängt, hat man entweder einen Punkt im Polyeder gefunden oder weiß, dass das Polyeder leer ist, weil es sonst größer sein müsste als das aktuelle Ellipsoid.

</p>

<div class="mw-heading mw-heading3"><h3 id="Weitere_Methoden">Weitere Methoden</h3></div>

<p>Für einige Klassen von linearen Programmen gibt es spezielle Algorithmen, die theoretisch oder praktisch schneller laufen als z. B. der Simplexalgorithmus. Ein Beispiel hierfür ist die <a href="Ungarische_Methode" title="Ungarische Methode">Ungarische Methode</a>, die auf Zuordnungsprobleme angewandt werden kann. Lineare Programme mit zwei Variablen lassen sich näherungsweise zeichnerisch lösen. Diese Methode hat aber hauptsächlich didaktischen Wert, da in der Praxis auftretende LPs leicht mehrere Hunderttausende Variablen besitzen können.

</p>

<div class="mw-heading mw-heading2"><h2 id="Dualität"><span id="Dualit.C3.A4t"></span>Dualität</h2></div>

<div class="mw-heading mw-heading3"><h3 id="Obere_Schranken">Obere Schranken</h3></div>

<p>Um zu verifizieren, dass eine gültige Lösung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"></span> optimal für ein lineares Programm ist, versucht man,

den Zielfunktionswert des Programms nach oben abzuschätzen. Für das obige Beispiel gilt etwa

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}+x_{2}\leq 150\;\Rightarrow \;500x_{1}+500x_{2}\leq 500\cdot 150=75000}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ba30b3f2111217d221000bdf4eab624626d1e382.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:54.344ex; height:2.509ex;" alt="{\displaystyle x_{1}+x_{2}\leq 150\;\Rightarrow \;500x_{1}+500x_{2}\leq 500\cdot 150=75000}" loading="lazy"></span></dd></dl>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{1}\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b1158db629080d417050d60fed774e0f12084231.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.645ex; height:2.509ex;" alt="{\displaystyle x_{1}\geq 0}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x_{2}\geq 0}">

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x_{2}\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/85ba01fd2d8b4788a6709f142a560910d8a3d5f2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:6.645ex; height:2.509ex;" alt="{\displaystyle x_{2}\geq 0}" loading="lazy"></span> folgt daraus, dass

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(x_{1},x_{2})=300x_{1}+500x_{2}\leq 500x_{1}+500x_{2}\leq 75000}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/337682428564dcba5079b9ff207a6719d6c8bdb0.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:53.711ex; height:2.843ex;" alt="{\displaystyle G(x_{1},x_{2})=300x_{1}+500x_{2}\leq 500x_{1}+500x_{2}\leq 75000}" loading="lazy"></span></dd></dl>

<p>Die Optimallösung kann somit keinen Zielfunktionswert größer als <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 75000}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 75000}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2fc19216288362c16220d0249ea1efd23ff62e2a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:5.812ex; height:2.176ex;" alt="{\displaystyle 75000}" loading="lazy"></span> haben. Eine bessere

Abschätzung erhält man, indem man <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 300}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 300}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1aa5eeafe495f318e96b1e8f8e4d7305bb940cdc.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 300}" loading="lazy"></span> Mal die zweite und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle 100}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle 100}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0572cd017c6d7936a12737c9d614a2f801f94a36.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:3.487ex; height:2.176ex;" alt="{\displaystyle 100}" loading="lazy"></span> Mal die dritte

Ungleichung addiert:

</p>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle G(x_{1},x_{2})=300x_{1}+500x_{2}\leq 300\cdot (x_{1}+x_{2})+100\cdot (3x_{2})=300x_{1}+600x_{2}\leq 63000}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ab8c0328027b889ea27cbf69c309a777cbc0d439.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:84.756ex; height:2.843ex;" alt="{\displaystyle G(x_{1},x_{2})=300x_{1}+500x_{2}\leq 300\cdot (x_{1}+x_{2})+100\cdot (3x_{2})=300x_{1}+600x_{2}\leq 63000}" loading="lazy"></span></dd></dl>

<p>Dieses Verfahren lässt sich leicht verallgemeinern: Wählt man für ein gegebenes LP in Standardform

<i>Multiplikatoren</i> <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\in \mathbb {R} _{+}^{m}}">

</mrow>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\in \mathbb {R} _{+}^{m}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/6326206da8e76ab1f218cf7a8931a5af9d4df4a2.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:7.349ex; height:3.009ex;" alt="{\displaystyle y\in \mathbb {R} _{+}^{m}}" loading="lazy"></span>, so ist jeder Vektor <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y^{T}A}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y^{T}A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/667df18b3db7188bbf2930533b16ebeb89afa017.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.293ex; height:3.009ex;" alt="{\displaystyle y^{T}A}" loading="lazy"></span> eine obere

Schranke, sofern <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y^{T}A\geq c^{T}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y^{T}A\geq c^{T}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/916f6e735b8c0810b5804240355781b502f03793.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.787ex; height:3.009ex;" alt="{\displaystyle y^{T}A\geq c^{T}}" loading="lazy"></span>. Dies entspricht einer

<a href="Konische_Kombination" title="Konische Kombination">konischen Kombination</a> der Spalten von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle A}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/7daff47fa58cdfd29dc333def748ff5fa4c923e3.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.743ex; height:2.176ex;" alt="{\displaystyle A}" loading="lazy"></span>. Die Bedingung

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y^{T}A\geq c^{T}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/916f6e735b8c0810b5804240355781b502f03793.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.787ex; height:3.009ex;" alt="{\displaystyle y^{T}A\geq c^{T}}" loading="lazy"></span> stellt sicher,

dass sich die Koeffizienten von <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle c^{T}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{T}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9f2d2c4fdbb8c88265eb2ca1a4509df7bd9d8913.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.396ex; height:2.676ex;" alt="{\displaystyle c^{T}}" loading="lazy"></span> für <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a2608e2b392b079f5b763f27bf52883dbee3b64a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.591ex; height:2.343ex;" alt="{\displaystyle x\geq 0}" loading="lazy"></span> gegen

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y^{T}A}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/667df18b3db7188bbf2930533b16ebeb89afa017.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:4.293ex; height:3.009ex;" alt="{\displaystyle y^{T}A}" loading="lazy"></span> abschätzen lassen. Der Zielfunktionswert der durch <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"></span> gegebenen obere Schranke ist

somit <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y^{T}b}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y^{T}b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/73feabfe31474db4628b1e1145b59583bac828c1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.547ex; height:3.009ex;" alt="{\displaystyle y^{T}b}" loading="lazy"></span>. Um die <i>beste</i> obere Schranke zu finden, kann man nun ein weiteres LP aufstellen:

</p>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min \;\{y^{T}b\,:\,y^{T}A\geq c^{T},\;y\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1cc0fa98c7c2d8c8e80ac6e2190c605631562996.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.987ex; height:3.176ex;" alt="{\displaystyle \min \;\{y^{T}b\,:\,y^{T}A\geq c^{T},\;y\geq 0\}}" loading="lazy"></span></dd></dl>

<p>Dieses LP nennt man das <i>duale Problem</i> zu dem <i>primalen Problem</i>

</p>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max \;\{c^{T}x\,:\,Ax\leq b,\;x\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0caa24f1cc3a49d7a723573c55652026000b4266.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.172ex; height:3.176ex;" alt="{\displaystyle \max \;\{c^{T}x\,:\,Ax\leq b,\;x\geq 0\}}" loading="lazy"></span></dd></dl>

<p>Die Einträge des Vektors <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"></span> werden als Multiplikatoren oder <i>Dualvariablen</i> bezeichnet. Die Dualität Linearer Programme ist ein Spezialfall der <a href="Lagrange-Dualit%C3%A4t" title="Lagrange-Dualität">Lagrange-Dualität</a>.

</p><p>Falls ein lineares Programm aus einem <a href="Kombinatorische_Optimierung" title="Kombinatorische Optimierung">kombinatorischen Optimierungsproblem</a> entsteht, so

hat das duale Programm oft eine anschauliche Interpretation; die nachfolgenden Sätze können dann auch benutzt werden,

um Resultate wie das <a href="Max-Flow-Min-Cut-Theorem" title="Max-Flow-Min-Cut-Theorem">Max-Flow-Min-Cut-Theorem</a> herzuleiten.

</p>

<div class="mw-heading mw-heading3"><h3 id="Dualisierung_beliebiger_linearer_Programme">Dualisierung beliebiger linearer Programme</h3></div>

<p>Für lineare Programme, welche nicht in Standardform vorliegen, gelten die folgenden Vorschriften zur

Dualisierung:

</p>

<th>primales LP</th>

<th>duales LP

</th></tr>

<tr>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max \;\{c^{T}x\,:\,Ax\leq b,\;x\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0caa24f1cc3a49d7a723573c55652026000b4266.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.172ex; height:3.176ex;" alt="{\displaystyle \max \;\{c^{T}x\,:\,Ax\leq b,\;x\geq 0\}}" loading="lazy"></span></td>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min \;\{y^{T}b\,:\,y^{T}A\geq c^{T},\;y\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1cc0fa98c7c2d8c8e80ac6e2190c605631562996.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.987ex; height:3.176ex;" alt="{\displaystyle \min \;\{y^{T}b\,:\,y^{T}A\geq c^{T},\;y\geq 0\}}" loading="lazy"></span>

</td></tr>

<tr>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max \;\{c^{T}x\,:\,Ax=b,\;x\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/630477c303c1188a0fcf8183ae6a2cddb1decd20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.172ex; height:3.176ex;" alt="{\displaystyle \max \;\{c^{T}x\,:\,Ax=b,\;x\geq 0\}}" loading="lazy"></span></td>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min \;\{y^{T}b\,:\,y^{T}A\geq c^{T}\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ba5d192503427242b179fa018050f5606510a732.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:22.891ex; height:3.176ex;" alt="{\displaystyle \min \;\{y^{T}b\,:\,y^{T}A\geq c^{T}\}}" loading="lazy"></span>

</td></tr>

<tr>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max \;\{c^{T}x\,:\,Ax\leq b\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/ccbdefe47453b5657b67b8731bdc12c9bfe4c1e1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.902ex; height:3.176ex;" alt="{\displaystyle \max \;\{c^{T}x\,:\,Ax\leq b\}}" loading="lazy"></span></td>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min \;\{y^{T}b\,:\,y^{T}A=c^{T},\;y\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/55408e2f0939dbefdbdd16ab58ed4356c99da478.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:29.987ex; height:3.176ex;" alt="{\displaystyle \min \;\{y^{T}b\,:\,y^{T}A=c^{T},\;y\geq 0\}}" loading="lazy"></span>

</td></tr></tbody></table>

<p>Für Minimierungsprobleme gilt analog:

</p>

<th>primales LP</th>

<th>duales LP

</th></tr>

<tr>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min \;\{c^{T}x\,:\,Ax\geq b,\;x\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/972b3dd52fd1e5c4abb0f305435c03270313acf1.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.721ex; height:3.176ex;" alt="{\displaystyle \min \;\{c^{T}x\,:\,Ax\geq b,\;x\geq 0\}}" loading="lazy"></span></td>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max \;\{y^{T}b\,:\,y^{T}A\leq c^{T},\;y\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/afb2b67cf432005067c4ddd35ecd8babb89a5c9f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.438ex; height:3.176ex;" alt="{\displaystyle \max \;\{y^{T}b\,:\,y^{T}A\leq c^{T},\;y\geq 0\}}" loading="lazy"></span>

</td></tr>

<tr>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min \;\{c^{T}x\,:\,Ax=b,\;x\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e3ee71d7cfa61a61ee838aedc38a414735c3e242.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:27.721ex; height:3.176ex;" alt="{\displaystyle \min \;\{c^{T}x\,:\,Ax=b,\;x\geq 0\}}" loading="lazy"></span></td>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max \;\{y^{T}b\,:\,y^{T}A\leq c^{T}\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/4aaafc682604e4b5ed8a1e8e80b5a921354630da.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:23.342ex; height:3.176ex;" alt="{\displaystyle \max \;\{y^{T}b\,:\,y^{T}A\leq c^{T}\}}" loading="lazy"></span>

</td></tr>

<tr>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \min \;\{c^{T}x\,:\,Ax\geq b\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/9c6cdd366342113a0e6f07410673c571848395ea.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:20.451ex; height:3.176ex;" alt="{\displaystyle \min \;\{c^{T}x\,:\,Ax\geq b\}}" loading="lazy"></span></td>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max \;\{y^{T}b\,:\,y^{T}A=c^{T},\;y\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8b108eb395ebf4014d52f9e3a59000eed21f9fa.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:30.438ex; height:3.176ex;" alt="{\displaystyle \max \;\{y^{T}b\,:\,y^{T}A=c^{T},\;y\geq 0\}}" loading="lazy"></span>

</td></tr></tbody></table>

<p>Im Allgemeinen gilt:

</p>

<th>primales LP</th>

<th>duales LP

</th></tr>

<tr>

<td>nichtnegative Variable</td>

<td>Ungleichung

</td></tr>

<tr>

<td>nicht vorzeichenbeschränkte Variable</td>

<td>Gleichung

</td></tr>

<tr>

<td>Ungleichung</td>

<td>nichtnegative Variable

</td></tr>

<tr>

<td>Gleichung</td>

<td>nicht vorzeichenbeschränkte Variable

</td></tr></tbody></table>

<p>Dabei ist zu beachten, dass bei Maximierungsproblemen die Ungleichungen stets in der Form

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Ax\leq b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/08249140bbb640be6c1242b705a896fb8951886f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.169ex; height:2.343ex;" alt="{\displaystyle Ax\leq b}" loading="lazy"></span> und bei Minimierungsproblemen in der Form

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Ax\geq b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/2123ee2e56394a9b16f0932e3dacebb0bcddbcf7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.169ex; height:2.343ex;" alt="{\displaystyle Ax\geq b}" loading="lazy"></span> aufgeschrieben werden.

</p>

<div class="mw-heading mw-heading3"><h3 id="Eigenschaften_des_dualen_Programms">Eigenschaften des dualen Programms</h3></div>

<p>Das primale und duale LP bilden ein <a href="Dualit%C3%A4t_(Mathematik)" title="Dualität (Mathematik)">duales</a> Paar, es gilt also, dass aus der

Dualisierung des dualen LP wieder das primale LP entsteht.

</p><p>Des Weiteren gilt für beliebige zulässige primale bzw. duale Lösungen <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,y}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5ea0abffd33a692ded22accc104515a032851dff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.519ex; height:2.009ex;" alt="{\displaystyle x,y}" loading="lazy"></span>:

</p>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{T}x\leq y^{T}Ax\leq y^{T}b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/95590a57550a05258438e9c0a54ce44a63b5e40d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:19.093ex; height:3.009ex;" alt="{\displaystyle c^{T}x\leq y^{T}Ax\leq y^{T}b}" loading="lazy"></span></dd></dl>

<p>Dabei gilt die erste Ungleichung, da <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/a2608e2b392b079f5b763f27bf52883dbee3b64a.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:5.591ex; height:2.343ex;" alt="{\displaystyle x\geq 0}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y^{T}A\geq c^{T}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y^{T}A\geq c^{T}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/916f6e735b8c0810b5804240355781b502f03793.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:9.787ex; height:3.009ex;" alt="{\displaystyle y^{T}A\geq c^{T}}" loading="lazy"></span> und die zweite,

weil <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Ax\leq b}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Ax\leq b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/08249140bbb640be6c1242b705a896fb8951886f.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.505ex; width:7.169ex; height:2.343ex;" alt="{\displaystyle Ax\leq b}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y\geq 0}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y\geq 0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/130e8795bc869a5b823133c5a0972693605c00bd.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.416ex; height:2.509ex;" alt="{\displaystyle y\geq 0}" loading="lazy"></span>. Dieses Resultat ist als der <i>schwache Dualitätssatz</i>

bekannt. Er entspricht der <a href="Schwache_Dualit%C3%A4t" class="mw-redirect" title="Schwache Dualität">schwachen Dualität</a> in der Lagrange-Dualität.

</p>

<div class="mw-heading mw-heading3"><h3 id="Der_starke_Dualitätssatz"><span id="Der_starke_Dualit.C3.A4tssatz"></span>Der starke Dualitätssatz</h3></div>

<p>Der <i>starke Dualitätssatz</i> verschärft die obige Aussage: Wenn eines der beiden LPs eine beschränkte Optimallösung besitzt, dann auch das andere, und die optimalen Zielfunktionswerte sind in diesem Fall gleich. Für jede optimale Lösung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e5be23ee5d433f8b576e63bcb47518128ee0b6bb.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:2.384ex; height:2.343ex;" alt="{\displaystyle x^{*}}" loading="lazy"></span> des primalen und jede optimale Lösung <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/3fcfcfa0fbced647ea73759c68ffd7a028729d62.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:2.215ex; height:2.676ex;" alt="{\displaystyle y^{*}}" loading="lazy"></span> des dualen Problems gilt also

</p>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{T}\;x^{*}=(y^{*})^{T}b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/cea281e5c13f6e04ec78bbfc33f03fd56c279a26.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:14.935ex; height:3.176ex;" alt="{\displaystyle c^{T}\;x^{*}=(y^{*})^{T}b}" loading="lazy"></span>.</dd></dl>

<p>Dies entspricht der <a href="Starke_Dualit%C3%A4t" class="mw-redirect" title="Starke Dualität">starken Dualität</a> in der Lagrange-Dualität. Man kann zeigen, dass folgende Zusammenhänge gelten:

</p>

<ul><li>Das duale Problem hat genau dann eine beschränkte Optimallösung, wenn das primale Problem eine beschränkte Optimallösung besitzt.</li>

<li>Wenn das primale Problem keine zulässige Lösung hat, ist das duale Problem unbeschränkt oder hat auch keine zulässige Lösung.</li>

<li>Wenn das primale Problem unbeschränkt ist, hat das duale Problem keine zulässige Lösung.</li></ul>

<p>Diese und weitere Sätze bilden die Grundlage für alle Verfahren, die mit primalen und dualen Schranken für den Wert einer Optimallösung arbeiten, wie beispielsweise <a href="Branch-and-Cut" title="Branch-and-Cut">Branch-and-Cut</a> und <a href="Schnittebenenverfahren" title="Schnittebenenverfahren">Schnittebenenverfahren</a>.

</p>

<div class="mw-heading mw-heading3"><h3 id="Der_Satz_vom_komplementären_Schlupf"><span id="Der_Satz_vom_komplement.C3.A4ren_Schlupf"></span>Der Satz vom komplementären Schlupf</h3></div>

<div class="hauptartikel" role="navigation"><span class="hauptartikel-pfeil" title="siehe" aria-hidden="true" role="presentation">→ </span><i><span class="hauptartikel-text">Hauptartikel</span>: <a href="Komplement%C3%A4rer_Schlupf" class="mw-redirect" title="Komplementärer Schlupf">Komplementärer Schlupf</a></i></div>

<p>Zusätzlich zu den obigen Zusammenhängen über die Lösbarkeit des primalen bzw. dualen Problems gilt die folgende Aussage:

</p><p>Falls sowohl das primale als auch das duale Problem zulässige Lösungen haben, so existiert

ein Paar <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x^{*},y^{*}}">

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x^{*},y^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8f62a2852203b55e87ac585ff97dbe27522027c5.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:5.633ex; height:2.676ex;" alt="{\displaystyle x^{*},y^{*}}" loading="lazy"></span> von Lösungen mit der Eigenschaft, dass

</p>

</mrow>

</mrow>

</msubsup>

<msub>

</mrow>

</msub>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}^{*}\cdot (b_{i}-(Ax^{*})_{i})=0\;\;\;\forall i=1,\ldots ,m}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0026215c8f6bfe933d19a1ec1daea7a0c2738b85.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:36.848ex; height:3.009ex;" alt="{\displaystyle y_{i}^{*}\cdot (b_{i}-(Ax^{*})_{i})=0\;\;\;\forall i=1,\ldots ,m}" loading="lazy"></span></dd></dl>

<p>Dies bedeutet, dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y_{i}^{*}>0\;\Rightarrow \;(Ax^{*})_{i}=b_{i}}">

</mrow>

</mrow>

</msubsup>

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y_{i}^{*}>0\;\Rightarrow \;(Ax^{*})_{i}=b_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/dd1a345bfd061ea91ae3c03f73e5391ad6b8c727.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:23.012ex; height:3.009ex;" alt="{\displaystyle y_{i}^{*}>0\;\Rightarrow \;(Ax^{*})_{i}=b_{i}}" loading="lazy"></span> und

umgekehrt <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (Ax^{*})_{i}<b_{i}\;\Rightarrow \;y_{i}^{*}=0}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

<msub>

</mrow>

</msub>

</mrow>

</mrow>

</msubsup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (Ax^{*})_{i}<b_{i}\;\Rightarrow \;y_{i}^{*}=0}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/1fd8bd1e147b468e42025af2c89450f9505ed503.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -1.005ex; width:23.012ex; height:3.009ex;" alt="{\displaystyle (Ax^{*})_{i}<b_{i}\;\Rightarrow \;y_{i}^{*}=0}" loading="lazy"></span>. Hierbei bezeichnet <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle (Ax^{*})_{i}}">

<msup>

</mrow>

</msup>

<msub>

</mrow>

</msub>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle (Ax^{*})_{i}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8644e0976bb663c750085c079e7a50e730f3c812.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:6.736ex; height:2.843ex;" alt="{\displaystyle (Ax^{*})_{i}}" loading="lazy"></span>

die <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle i}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle i}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/add78d8608ad86e54951b8c8bd6c8d8416533d20.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:0.802ex; height:2.176ex;" alt="{\displaystyle i}" loading="lazy"></span>-te Komponente des Vektors <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle Ax^{*}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle Ax^{*}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/e863dcbc4f08604d1e4d082e7e25b9e13787d4d9.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:4.127ex; height:2.343ex;" alt="{\displaystyle Ax^{*}}" loading="lazy"></span>.

</p><p>Diese Lösungen sind auch optimal, da in

diesem Fall die obigen Ungleichungen mit Gleichheit erfüllt sind:

</p>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle c^{T}x^{*}=(y^{*})^{T}Ax^{*}=(y^{*})^{T}b}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/8d6c67bd2bc8de3379cf18527c543213dfcead0c.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:26.928ex; height:3.176ex;" alt="{\displaystyle c^{T}x^{*}=(y^{*})^{T}Ax^{*}=(y^{*})^{T}b}" loading="lazy"></span>.</dd></dl>

<p>Diese zusätzliche Eigenschaft wird zum Beispiel bei primal-dualen Algorithmen ausgenutzt, um die Optimalität einer

Lösung zu verifizieren.

</p>

<div class="mw-heading mw-heading3"><h3 id="Äquivalenz_von_Optimierungs-_und_Zulässigkeitsproblemen"><span id=".C3.84quivalenz_von_Optimierungs-_und_Zul.C3.A4ssigkeitsproblemen"></span>Äquivalenz von Optimierungs- und Zulässigkeitsproblemen</h3></div>

<p>Der starke Dualitätssatz ermöglicht es ebenfalls, Optimierungsprobleme auf Zulässigkeitsprobleme zu reduzieren:

Anstatt das Problem <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle \max \;\{c^{T}x\,:\,Ax\leq b,\;x\geq 0\}}">

<msup>

</mrow>

</msup>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle \max \;\{c^{T}x\,:\,Ax\leq b,\;x\geq 0\}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/0caa24f1cc3a49d7a723573c55652026000b4266.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.838ex; width:28.172ex; height:3.176ex;" alt="{\displaystyle \max \;\{c^{T}x\,:\,Ax\leq b,\;x\geq 0\}}" loading="lazy"></span> zu lösen, kann man ebenso gut

ein Paar von Lösungen finden, die den folgenden Bedingungen gehorchen:

</p>

<mtr>

<mtd>

</mtd>

<mtd>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

<mtr>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

<mtd>

<msup>

</mrow>

</msup>

</mtd>

</mtr>

</mtable>

</mrow>

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle {\begin{aligned}Ax&\leq b,\;x\geq 0\\y^{T}A&\geq c^{T},\;y\geq 0\\c^{T}x&\geq y^{T}b\\\end{aligned}}}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/359122b46414aa1ed4d8134936d958e656d1fae7.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -3.828ex; margin-bottom: -0.176ex; width:17.634ex; height:9.176ex;" alt="{\displaystyle {\begin{aligned}Ax&\leq b,\;x\geq 0\\y^{T}A&\geq c^{T},\;y\geq 0\\c^{T}x&\geq y^{T}b\\\end{aligned}}}" loading="lazy"></span></dd></dl>

<p>Dabei stellen die ersten beiden Bedingungen sicher, dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> eine zulässige Lösung des Problems ist, während die nächsten Bedingungen dafür sorgen,

dass <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"></span> gültig für das duale Programm ist. Die letzte Ungleichung wird nur von solchen Lösungspaaren <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x,y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x,y}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/5ea0abffd33a692ded22accc104515a032851dff.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:3.519ex; height:2.009ex;" alt="{\displaystyle x,y}" loading="lazy"></span> erfüllt, deren Zielfunktionswerte übereinstimmen.

Dies ist genau dann der Fall, wenn es sich bei <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle x}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle x}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/87f9e315fd7e2ba406057a97300593c4802b53e4.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.338ex; width:1.33ex; height:1.676ex;" alt="{\displaystyle x}" loading="lazy"></span> und <span class="mwe-math-element mwe-math-element-inline"><span class="mwe-math-mathml-inline mwe-math-mathml-a11y" style="display: none;"><math xmlns="http://www.w3.org/1998/Math/MathML" alttext="{\displaystyle y}">

</mstyle>

</mrow>

<annotation encoding="application/x-tex">{\displaystyle y}</annotation>

</semantics>

</math></span><img src="./_assets_/eb734a37dd21ce173a46342d1cc64c92/b8a6208ec717213d4317e666f1ae872e00620a0d.svg" class="mwe-math-fallback-image-inline mw-invert skin-invert" aria-hidden="true" style="vertical-align: -0.671ex; width:1.155ex; height:2.009ex;" alt="{\displaystyle y}" loading="lazy"></span> um die Optimallösungen der beiden Probleme handelt.

Das obige Optimierungsproblem hat damit eine Optimallösung genau dann wenn der obige Polyeder nicht leer ist.

Offensichtlich kann man die Zulässigkeit eines Problems auch durch Lösung eines Optimierungsproblems entscheiden, man wählt dazu beispielsweise den <a href="Nullvektor" title="Nullvektor">Nullvektor</a> als

Zielfunktion. Damit sind lineare Optimierungsprobleme und Zulässigkeitsprobleme von Polyedern äquivalent bezüglich ihrer <a href="Komplexit%C3%A4tstheorie" title="Komplexitätstheorie">Zeitkomplexität</a>.

</p>

<div class="mw-heading mw-heading2"><h2 id="Literatur">Literatur</h2></div>

<ul><li><a href="Robert_Bixby" title="Robert Bixby">Robert Bixby</a>: <i>Solving real-world linear programs: A decade and more of progress.</i> In: <i>Operations Research.</i> Band 50, Nr. 1, 2002, S. 3–15.</li>

<li><a href="George_Dantzig" title="George Dantzig">George B. Dantzig</a>: <i>Lineare Programmierung und Erweiterungen.</i> Springer, 1966. (Originalausgabe: <i>Linear Programming and Extensions.</i> Rand Corp., Santa Monica 1959)</li>

<li><a href="Va%C5%A1ek_Chv%C3%A1tal" title="Vašek Chvátal">Vašek Chvátal</a>: <i>Linear Programming.</i> Freeman, New York 1983, ISBN 0-7167-1587-2.</li>

<li><a href="Alexander_Schrijver" title="Alexander Schrijver">Alexander Schrijver</a>: <i>Theory of Linear and Integer Programming.</i> Wiley, 1998, ISBN 0-471-98232-6.</li>

<li><a href="Peter_Knabner" title="Peter Knabner">Peter Knabner</a>, <a href="Wolf_Barth_(Mathematiker)" title="Wolf Barth (Mathematiker)">Wolf Barth</a>: <i>Lineare Algebra. Grundlagen und Anwendungen.</i> Springer Spektrum, Berlin/Heidelberg 2013, ISBN 978-3-642-32185-6.</li>

<li>F. L. Hitchcock: <i>The distribution of a product from several sources to numerous localities.</i> In: <i>Journal of Mathematical Physics.</i> Band 20, 1941, S. 224–230.</li>

<li><a href="Leonid_Witaljewitsch_Kantorowitsch" title="Leonid Witaljewitsch Kantorowitsch">Leonid Kantorowitsch</a>: <i>Mathematical Methods of Organizing and Planning Production.</i> In: <i>Management Science.</i> Vol. 6, No. 4, 1960, S. 366–422. <a rel="nofollow" class="external text" href="http://www.jstor.org/stable/2627082">(online auf: <i>jstor.org</i>)</a></li>

<li>Klaus Hagendorf: <i>OpenOffice calc Solver Lösungen der Beispiele in Kantorowitschs Artikel von 1939.</i> <a rel="nofollow" class="external text" href="http://eurodos.free.fr/docu/econ/Kantorovich1939.zip">(online auf: <i>eurodos.free.fr</i>, ZIP; 521 kB)</a></li>

<li><a href="Wolfgang_Domschke" title="Wolfgang Domschke">Wolfgang Domschke</a>, Andreas Drexl, Robert Klein, Armin Scholl: <i>Einführung in Operations Research.</i> 9. Auflage. Springer, Berlin 2015, ISBN 978-3-662-48215-5, Kapitel 2</li></ul>

<div class="mw-heading mw-heading2"><h2 id="Einzelnachweise">Einzelnachweise</h2></div>

<li id="cite_note-1"><span class="mw-cite-backlink"><a href="#cite_ref-1">↑</a></span> <span class="reference-text"><a rel="nofollow" class="external text" href="http://www.jstor.org/stable/2627082"><i>Mathematical Methods of Organizing and Planning Production.</i></a> (PDF; 1,4 MB). In: <i>Management Science.</i> Band 6, Nr. 4 (Juli 1960), S. 366–422.</span>

</li>

<li id="cite_note-2"><span class="mw-cite-backlink"><a href="#cite_ref-2">↑</a></span> <span class="reference-text">Heiner Müller-Merbach: <i>Operations Research.</i> 3. Auflage. Verlag Franz Vahlen, München 1973, ISBN 3-8006-0388-8, S. 89.</span>

</li>

<li id="cite_note-3"><span class="mw-cite-backlink"><a href="#cite_ref-3">↑</a></span> <span class="reference-text"><span class="cite">Robert E. Bixby: <a rel="nofollow" class="external text" href="https://web.archive.org/web/20170705143141/https://www.math.uni-bielefeld.de/documenta/vol-ismp/25_bixby-robert.pdf"><i>A brief history of linear and mixed-integer programming computation.</i></a> In: <i>In: Optimization Stories. EMS Press, 2012, ISBN 978-3-936609-58-5, S. 107–121.</i> Archiviert vom <style data-mw-deduplicate="TemplateStyles:r250917974">

/* start https://de.wikipedia.org/ */

.mw-parser-output .dewiki-iconexternal>a{background-position:center right!important;background-repeat:no-repeat!important}body.skin-minerva .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/OOjs_UI_icon_external-link-ltr-progressive.svg")!important;background-size:10px!important;padding-right:13px!important}body.skin-timeless .mw-parser-output .dewiki-iconexternal>a,body.skin-monobook .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/MediaWiki_external_link_icon.svg")!important;padding-right:13px!important}body.skin-vector .mw-parser-output .dewiki-iconexternal>a{background-image:url("./_mw_/Link.ernal-small-ltr-progressive.svg")!important;background-size:0.857em!important;padding-right:1em!important}

/* end https://de.wikipedia.org/ */

</style><span class="dewiki-iconexternal"><a class="external text" href="https://redirecter.toolforge.org/?url=https%3A%2F%2Fwww.math.uni-bielefeld.de%2Fdocumenta%2Fvol-ismp%2F25_bixby-robert.pdf">Original</a></span> am <span style="white-space:nowrap;">5. Juli 2017</span><span>;</span><span class="Abrufdatum"> abgerufen am 11. Juni 2025</span>.</span><span style="display: none;" class="Z3988" title="ctx_ver=Z39.88-2004&rft_val_fmt=info%3Aofi%2Ffmt%3Akev%3Amtx%3Adc&rfr_id=info%3Asid%2Fde.wikipedia.org%3ALineare+Optimierung&rft.title=A+brief+history+of+linear+and+mixed-integer+programming+computation&rft.description=A+brief+history+of+linear+and+mixed-integer+programming+computation&rft.identifier=https%3A%2F%2Fweb.archive.org%2Fweb%2F20170705143141%2Fhttps%3A%2F%2Fwww.math.uni-bielefeld.de%2Fdocumenta%2Fvol-ismp%2F25_bixby-robert.pdf&rft.creator=Robert+E.+Bixby&rft.source=https://www.math.uni-bielefeld.de/documenta/vol-ismp/25_bixby-robert.pdf"> </span></span>

</li>

<li id="cite_note-4"><span class="mw-cite-backlink"><a href="#cite_ref-4">↑</a></span> <span class="reference-text">N. Karmarkar: <i>A new polynomial-time algorithm for linear programming</i>. Combinatorica 4 (1984), Nr. 4, 373–395.</span>

</li>

<li id="cite_note-5"><span class="mw-cite-backlink"><a href="#cite_ref-5">↑</a></span> <span class="reference-text">Harvey J. Greenberg: <i>Klee-Minty Polytope Shows Exponential Time Complexity of Simplex Method.</i> University of Colorado at Denver, 1997 (<a rel="nofollow" class="external text" href="https://web.archive.org/web/20070927205456/http://glossary.computing.society.informs.org/notes/Klee-Minty.pdf">PDF</a>), Archivlink</span>

</li>

</ol></div><div><div class="zim-footer">

Dieser Artikel wurde von <a class="external text" title="Zuletzt bearbeitet am 2025-10-13" href="https://de.wikipedia.org/wiki/?title=Lineare_Optimierung&oldid=260554878">Wikipedia</a> herausgegeben. Der Text ist unter <a class="external text" href="https://creativecommons.org/licenses/by-sa/4.0/deed.de">Creative Commons Attribution-Share Alike 4.0</a> verfügbar, sofern nicht anders angegeben. Für die Mediendateien können zusätzliche Bedingungen gelten.

</div>

</div></div>

</div>

</main>

</div>

</body></html>